<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-29 17:07:51
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-30 10:16:16
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二分法查找</title>
</head>

<body>
    <script>
        // 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 - 1。

        // 这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素,满足二分查找法，
        // 是while(left < right)还是while(left <= right)还是right = middle还是right = middle - 1，问题最大的就是区间包含与否，二分法还要求不能有重复数据，而且是有序数组

        // 二分查找一般是[left,right),[left,right]两种，
        // 第一种定义target在左闭右闭的区间里[left,right]
        // 区间的定义决定了二分法如何书写
        // [left,right]有两点
        // 1）while(left<=right)使用的是小于等于（<=）因为left==right是有意义的所以要使用<=
        // 2) if(nums[middle] > target)right要赋值middle-1.因为当前这个nums[middle]一定不是target,接下来的左区间就是middle-1

        var search = function (nums, target) {
            let left = 0, right = nums.length - 1;
            while (left <= right) {
                // parseInt取整,否则这块有可能是小数也可以使用Math.floor(((right - left) / 2))
                let middle = left + Number.parseInt(((right - left) / 2));
                if (nums[middle] > target) {
                    right = middle - 1;
                }
                else if (nums[middle] < target) {
                    left = middle + 1;
                } else {
                    return middle;
                }
            }
            return -1;
        }



        // 二分法的第二种写法
        // target在一个左闭右开的区间里面，也就是[left,right)如果是这样的方式处理结果也有不同，
        // 也需要注意如下两点：
        // while(left<right)这里使用<因为left==right 在区间，[left,right)是没有意义的。
        // if(nums[middle]>target) right更新为middle因为当前nums[middle]不等于target左区间继续找，寻找区间是左闭右开区间，所right更新问middle。下一个区间不会比对nums[middle]

        var search = function (nums, target) {
            let left = 0, right = nums.length;
            while (left < right) {
                let mid = left + Math.floor((right - left) / 2);
                if (nums[mid] > target) {
                    right = mid;
                }
                else if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }

    </script>
</body>

</html>